Формулы

Логические эквивалентности

• Эквивалентность импликации (implication equivalence): \(P → Q \equiv ¬P ∨ Q\)
• Эквивалентность эквиваленции (biconditional equivalence): \(P ↔ Q \equiv (P → Q) ∧ (Q → P) \equiv (¬P ∨ Q) ∧ (P ∨ ¬Q)\)
• Закон тождества (identity law): \(p \lor 0 \equiv p\)
• Закон тождества (identity law): \(p \land 1 \equiv p\)
• Закон дополнения (complement law): \(p \lor \neg p \equiv 1\)
• Закон дополнения (complement law): \(p \land \neg p \equiv 0\)
• Идемпотентность (idempotent law): \(p \land p \equiv p\)
• Идемпотентность (idempotent law): \(p \lor p \equiv p\)
• Двойное отрицание (double negation law): \(\neg(\neg p) \equiv p\)
• Ассоциативность (associative law): \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
• Дистрибутивность (distributive law): \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
• Дистрибутивность (distributive law): \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
• Законы де Моргана (De Morgan’s law): \(\neg(p \land q) \equiv \neg p \lor \neg q\)
• Законы де Моргана (De Morgan’s law): \(\neg(p \lor q) \equiv \neg p \land \neg q\)
• Эквивалентность эквиваленции (bi-implication equivalence): \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
• Закон смежности (adjacency law): \(p \lor (\neg p \land q) \equiv p \lor q\)
• Закон упрощения (simplification law): \((p \lor q) \land (p \lor \neg q) \equiv p\)
• Эквивалентность контрапозиции (contrapositive equivalence): \(A \to B \equiv \neg B \to \neg A\)

Нормальные формы (DNF, CNF, ANF)

• Общая формула для DNF (disjunctive normal form): \[f = \bigvee_{f(\sigma_1, ..., \sigma_n)=1} (x_1^{\sigma_1} \land ... \land x_n^{\sigma_n})\]
• Общая формула для CNF (conjunctive normal form): \[f = \bigwedge_{f(\sigma_1, ..., \sigma_n)=0} (x_1^{\overline{\sigma_1}} \lor ... \lor x_n^{\overline{\sigma_n}})\]
• Конъюнкция в ANF (algebraic normal form): \(p \land q \equiv pq\)
• Отрицание в ANF: \(\neg p \equiv p \oplus 1\)
• Дизъюнкция в ANF: \(p \lor q \equiv p \oplus q \oplus pq\)
• Импликация в ANF: \(p \to q \equiv 1 \oplus p \oplus pq\)
• Эквиваленция в ANF: \(p \leftrightarrow q \equiv 1 \oplus p \oplus q\)
• Свойство ANF (идемпотентность умножения): \(p \cdot p \equiv p\)
• Свойство ANF (XOR с самим собой): \(p \oplus p \equiv 0\)
• Свойство ANF (тождественный элемент XOR): \(p \oplus 0 \equiv p\)

Логика предикатов (predicate logic)

• Закон де Моргана для квантора всеобщности: \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)
• Закон де Моргана для квантора существования: \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)
• Ограниченный квантор всеобщности (restricted universal): \(∀x∈A P(x) ≡ ∀x (A(x) → P(x))\)
• Ограниченный квантор существования (restricted existential): \(∃x∈A P(x) ≡ ∃x (A(x) ∧ P(x))\)

Теория множеств (set theory)

• Дополнение (complement): \(\overline{A} = U \setminus A\)
• Разность (difference): \(A \setminus B = A \cap \overline{B}\)
• Закон де Моргана: \(\overline{(A \cup B)} = \overline{A} \cap \overline{B}\)
• Закон де Моргана: \(\overline{(A \cap B)} = \overline{A} \cup \overline{B}\)
• Дистрибутивность: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
• Мощность объединения двух множеств (cardinality of a union, two sets): \(|A \cup B| = |A| + |B| - |A \cap B|\)
• Мощность объединения трёх множеств (cardinality of a union, three sets): \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \]
• Мощность разности множеств (cardinality of a set difference): \(|A \setminus B| = |A| - |A \cap B|\)
• Мощность декартова произведения (cardinality of a Cartesian product): \(|A \times B| = |A| \cdot |B|\)
• Пересечение декартовых произведений (intersection of Cartesian products): \((A \times C) \cap (B \times D) = (A \cap B) \times (C \cap D)\)
• Пересечение булеанов (intersection of power sets): \(P(A) \cap P(B) = P(A \cap B)\)

Доказательства и теория чисел (proofs and number theory)

• Определение нечётного целого: \(n = 2k + 1\)
• Определение чётного целого: \(n = 2k\)
• Сумма первых \(n\) целых (sum of first \(n\) integers): \[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
• Сумма первых \(n\) квадратов (sum of first \(n\) squares): \[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \]
• Сумма геометрической прогрессии (sum of a geometric series): \[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]
• Рекуррентное соотношение для чисел Фибоначчи (Fibonacci recurrence): \(f_n = f_{n-1} + f_{n-2}\)
• Формула Бине (Binet’s formula): \[ f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]
• Сумма первых \(n\) чисел Фибоначчи с нечётными индексами: \(f_1 + f_3 + \dots + f_{2n-1} = f_{2n}\)
• Неравенство Бернулли (Bernoulli’s inequality): \((1 + x)^n \ge 1 + xn\)

Комбинаторика (combinatorics)

• Упорядоченная выборка с повторениями (ordered arrangement with repetition): \(n^k\)
• Упорядоченная выборка без повторений (перестановка, permutation): \[P(n, k) = \frac{n!}{(n-k)!}\]
• Перестановка \(n\) различных объектов: \(n!\)
• Неупорядоченная выборка без повторений (сочетание, combination): \[C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]
• Разбиение на неупорядоченные группы (partitioning into unordered groups): \[\frac{C(n, k_1) \times C(n-k_1, k_2) \times \dots}{m!}\]
• Перестановки с повторениями (мультиномиальный коэффициент, multinomial coefficient): \[\frac{n!}{n_1!n_2!\dots n_k!}\]
• Коэффициент при \(x^{j}y^{k}\) в \((ax+by)^n\): \[\binom{n}{k} a^{j} b^k\]
• Коэффициент при \(x_1^{k_1} \dots x_m^{k_m}\) в \((c_1x_1 + \dots + c_mx_m)^n\): \[\binom{n}{k_1, k_2, \dots, k_m} c_1^{k_1} c_2^{k_2} \dots c_m^{k_m}\]
• Неупорядоченная выборка с повторениями (stars and bars): \[C(n+k-1, k) = \binom{n+k-1}{k}\]
• Число решений \(x_1 + \dots + x_k = n\) при \(x_i \ge 0\): \[C(n+k-1, k-1) = \binom{n+k-1}{k-1}\]
• Дополняющее пересчитывание (complementary counting): \(|A| = |Total| - |\overline{A}|\)

Рекуррентные соотношения (recurrence relations)

• Арифметическая прогрессия (arithmetic progression): \(a_n = a_0 + nd\)
• Геометрическая прогрессия (geometric progression): \(a_n = a_0 \cdot t^n\)
• Общее решение линейного рекуррентного соотношения 2-го порядка (различные корни \(p_1, p_2\)): \(a_n = c_1 p_1^n + c_2 p_2^n\)
• Общее решение при кратном корне \(p\): \(a_n = (c_1 n + c_2) p^n\)

Отношения и теория графов (relations and graph theory)

• Число всех бинарных отношений на \(n\) элементах (total number of binary relations): \(2^{n^2}\)
• Число рефлексивных отношений на \(n\) элементах: \(2^{n(n-1)}\)
• Число иррефлексивных отношений на \(n\) элементах: \(2^{n(n-1)}\)
• Число симметричных отношений на \(n\) элементах: \(2^{\frac{n(n+1)}{2}}\)
• Число асимметричных отношений на \(n\) элементах: \(3^{\frac{n(n-1)}{2}}\)
• Число антисимметричных отношений на \(n\) элементах: \(2^n \cdot 3^{\frac{n(n-1)}{2}}\)
• Число линейных порядков на \(n\) элементах (linear orders): \(n!\)
• Эквивалентность для асимметричного отношения (asymmetric relation equivalence): asymmetric \(\iff\) anti-symmetric \(\land\) irreflexive (асимметрично \(\iff\) антисимметрично \(\land\) иррефлексивно)
• Нестрогий порядок из строгого (non-strict from strict order): \(x \leq y \equiv (x < y \lor x = y)\)
• Лемма о рукопожатиях (handshaking lemma): \(\sum_{v \in V_G} d_G(v) = 2|E_G|\) (сумма степеней вершин равна удвоенному числу рёбер)
• Число рёбер в полном графе \(K_n\): \(|E| = \binom{n}{2} = \frac{n(n-1)}{2}\)
• Степени вершин в \(K_n\): каждая вершина имеет степень \(n-1\)
• Степени вершин в \(C_n\): каждая вершина имеет степень 2
• Число рёбер в \(C_n\): \(|E| = n\)
• Число рёбер в полном двудольном графе \(K_{n,m}\): \(|E| = nm\)
• Характеристическое свойство дерева (characteristic property of trees): связный граф с \(n\) вершинами является деревом тогда и только тогда, когда в нём ровно \(n-1\) ребро
• Число рёбер в лесу (forest): лес с \(n\) вершинами и \(k\) компонентами связности имеет ровно \(n-k\) рёбер
• Число простых графов порядка \(n\): \(2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}\) (каждое потенциальное ребро либо есть, либо нет)
• Число двудольных графов с долями \(|U|=n\) и \(|V|=m\): \(2^{nm}\) (каждое потенциальное ребро между долями либо есть, либо нет)

Эйлеровы и гамильтоновы графы (Eulerian and Hamiltonian graphs)

• Условие существования эйлерова цикла (Euler cycle condition): нетривиальный связный граф эйлеров тогда и только тогда, когда степень каждой вершины чётна
• Условие существования эйлерова пути (Euler path condition): у связного графа есть эйлеров путь тогда и только тогда, когда вершин нечётной степени ровно ноль или ровно две
• Полный граф и эйлеровость (complete graph Eulerian): \(K_n\) эйлеров тогда и только тогда, когда \(n\) нечётно
• Полный двудольный граф и эйлеровость (complete bipartite graph Eulerian): \(K_{n,m}\) эйлеров тогда и только тогда, когда \(n\) и \(m\) чётны
• Полный двудольный граф и гамильтоновость (complete bipartite graph Hamiltonian): \(K_{n,m}\) гамильтонов тогда и только тогда, когда \(n = m \geq 2\)
• Теорема Дирака (достаточное условие гамильтоновости, Dirac’s theorem): пусть \(G\) — простой граф с \(n \geq 3\) вершинами. Если \(\deg(v) \geq \frac{n}{2}\) для каждой вершины \(v\), то \(G\) гамильтонов
• Теорема Оре (достаточное условие гамильтоновости, Ore’s theorem): пусть \(G\) — простой граф с \(n \geq 3\) вершинами. Если \(\deg(u) + \deg(v) \geq n\) для каждой пары несмежных вершин \(u\) и \(v\), то \(G\) гамильтонов

Планарные графы и раскраски (planar graphs and colourings)

• Формула Эйлера для планарных графов (Euler’s formula): \(v - e + f = 2\), где \(v\) — число вершин, \(e\) — рёбер, \(f\) — граней (включая внешнюю)
• Ограничение на число рёбер планарного графа (edge bound for planar graphs): если \(G\) — связный планарный граф и \(v \geq 3\), то \(e \leq 3v - 6\)
• Ограничение для планарного двудольного графа (edge bound for bipartite planar graphs): если \(G\) — связный планарный двудольный граф и \(v \geq 3\), то \(e \leq 2v - 4\)
• Неравенство «грань–ребро» (общий случай, face-edge inequality): \(3f \leq 2e\) (у каждой грани не меньше 3 рёбер на границе, каждое ребро инцидентно не более чем двум граням)
• Неравенство «грань–ребро» (двудольный случай): \(4f \leq 2e\) (в двудольном графе нет треугольников, значит у каждой грани не меньше 4 рёбер)
• Хроматическое число полного графа (chromatic number of complete graph): \(\chi(K_n) = n\)
• Хроматическое число пустого графа (chromatic number of null graph): \(\chi(O_n) = 1\) (граф без рёбер)
• Хроматическое число двудольного графа (chromatic number of bipartite graph): \(\chi(G) = 2\) для любого нетривиального двудольного графа \(G\)
• Хроматическое число нечётного цикла (chromatic number of odd cycle): \(\chi(C_{2k+1}) = 3\)
• Хроматическое число чётного цикла (chromatic number of even cycle): \(\chi(C_{2k}) = 2\)
• Теорема о четырёх красках (four colour theorem): \(\chi(G) \leq 4\) для любого планарного графа \(G\)
• Теорема Куратовского (Kuratowski’s theorem): граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного \(K_5\) или \(K_{3,3}\)